#include <iostream>
#include <queue>
#include <unordered_map>
#include <vector>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

unordered_map<int, int> num2index;

TreeNode* makeTree(const vector<int>& pre,
                   const vector<int>& vin,
                   int f1,
                   int t1,
                   int f2,
                   int t2) {
    if (t1 < f1) return nullptr;
    TreeNode* root = new TreeNode(pre[f1]);
    int sep = num2index[pre[f1]];
    int leftSize = sep - f2;
    root->left = makeTree(pre, vin, f1 + 1, f1 + 1 + leftSize - 1, f2,
                          f2 + leftSize - 1);
    root->right = makeTree(pre, vin, f1 + leftSize + 1, t1, sep + 1, t2);
    return root;
}


TreeNode* reConstructBinaryTree(vector<int> pre, vector<int> vin) {
    for (int i = 0; i < vin.size(); i++) num2index[vin[i]] = i;
    return makeTree(pre, vin, 0, pre.size() - 1, 0, vin.size() - 1);
}

vector<string> traverse(TreeNode* root) {
    vector<string> ret;
    if (!root) return ret;
    // cout << 111111;
    queue<TreeNode*> Q;
    Q.push(root);
    while (!Q.empty()) {
        int sz = Q.size();
        for (int i = 0; i < sz; i++) {
            TreeNode* front = Q.front();
            Q.pop();
            if (front) {
                Q.push(front->left);
                Q.push(front->right);
                ret.push_back(to_string(front->val));
            } else {
                ret.push_back("#");
            }
        }
    }
    return ret;
}

int main() {
    vector<int> pre = {1, 2, 4, 7, 3, 5, 6, 8};
    vector<int> vin = {4, 7, 2, 1, 5, 3, 8, 6};

    TreeNode* root = reConstructBinaryTree(pre, vin);

    vector<string> aaa = traverse(root);

    for (int i = 0; i < aaa.size(); i++) cout << aaa[i] << ", ";

    return 0;
}